import java.util.Arrays;

/**
 * Created by Administrator on 2017/2/15.
 */
public class Test2 {

    public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int[] flag = new int[matrix.length];
                if (hasPath(matrix, rows, cols, str, i, j, 0, flag)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean hasPath(char[] matrix, int rows, int cols, char[] str, int i, int j, int k, int[] flag) {
        int index = cols * i + j;
        if (index >= matrix.length || i < 0 || j < 0 || i > rows || j > cols || flag[index] == 1 || matrix[index] != str[k]) {
            return false;
        }
        if (k == str.length - 1) {
            return true;
        }
        if (matrix[index] == str[k]) {
            flag[index] = 1;
            //左
            return hasPath(matrix, rows, cols, str, i, j - 1, k + 1, flag) ||
                    //下
                    hasPath(matrix, rows, cols, str, i + 1, j, k + 1, flag) ||
                    //右
                    hasPath(matrix, rows, cols, str, i, j + 1, k + 1, flag) ||
                    //上
                    hasPath(matrix, rows, cols, str, i - 1, j, k + 1, flag);

        }
        return false;
    }

    public static void main(String[] args) {
        Test2 test2 = new Test2();
        char[] chs = "ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS".toCharArray();
        char[] str = "SGGFIECVAASABCEHJIGQEM".toCharArray();
        System.out.println(test2.hasPath(chs, 5, 8, str));
    }


}
